
//1.蛇形填数 
//#include <iostream>
//using namespace std;
//const int N = 100;
//int a[N][N];
//int main()
//{
//    int flag = 0;
//    int i = 1, j = 1;
//    a[1][1] = 1;
//    bool f = false;
//    while (true)
//    {
//        //右移
//        if (flag % 4 == 0)
//        {
//            j++;
//            a[i][j] = a[i][j - 1] + 1;
//            flag++;
//            if (i == 20 && j == 20)f = true;
//        }
//        //左下移
//        while (flag % 4 == 1)
//        {
//            i++;
//            j--;
//            a[i][j] = a[i - 1][j + 1] + 1;
//            if (i != 1 && j == 1)flag++;
//            if (i == 20 && j == 20)f = true;
//        }
//
//        //下移
//        if (flag % 4 == 2)
//        {
//            i++;
//            a[i][j] = a[i - 1][j] + 1;
//            flag++;
//            if (i == 20 && j == 20)f = true;
//        }
//
//        //右上移
//        while (flag % 4 == 3)
//        {
//            i--;
//            j++;
//            a[i][j] = a[i + 1][j - 1] + 1;
//            if (i == 1 && j != 1)flag++;
//            if (i == 20 && j == 20)f = true;
//        }
//
//        if (f)break;
//    }
//    
//    
//
//    cout << endl << a[20][20];
//    return 0;
//}



//
//#include <iostream>
//using namespace std;
//const int n=1e4+10;
//char arr[n][n];
//bool st[n][n];
//bool flag=false;
//int cnt=0;
//int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
//void dfs(int x,int y)
//{
//  if(st[x][y]=='*'||arr[x][y]!='#')return;
//  st[x][y]='*';
//  
//  if(arr[x-1][y]=='#'&&arr[x+1][y]=='#'&&arr[x][y-1]=='#'&&arr[x][y+1]=='#')flag=true;
//
//  for(int i=0;i<4;i++)
//  {
//    int nx=x+d[i][0];
//    int ny=y+d[i][1];
//    dfs(nx,ny);
//  }
//  
//}
//int main()
//{
//  int N;
//  cin>>N;
//  for(int i=1;i<=N;i++)
//  {
//    for(int j=1;j<=N;j++)
//    {
//      cin>>arr[i][j];
//    }
//  }
//
//  for(int i=1;i<=N;i++)
//  {
//    for(int j=1;j<=N;j++)
//    {
//      if(arr[i][j]=='#'&&st[i][j]!='*')
//      {
//        flag=false;
//        dfs(i,j);
//        if(flag==false)cnt++;
//      }
//    }
//  }
//  cout<<cnt;
//  return 0;
//}



// 全球变暖	 
//#include <bits/stdc++.h>
//using namespace std;
//
//const int n=1e3+10;
//char Map[n][n];
//bool st[n][n];
//int record[n][n];
//
//int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
//
//struct Node
//{
//	Node()
//	{
//	}
//	Node(int x,int y,int bits,int flag):x_(x),y_(y),bits_(bits),flag_(flag) 
//	{
//	}
//  int x_,y_,bits_,flag_;  
//};
//queue<Node> q;
//
//void bfs(Node p,int k)
//{
//    Node t,tt;
//    
//    q.push(p);//放入第一个元素
//    while(!q.empty())
//    {
//        t=q.front();
//        q.pop();//对首出列,todo与对首相邻且满足条件的入列
//        st[t.x_][t.y_]=1;//标记位使用过
//        for(int i=0;i<4;i++)
//        {
//            tt=t;
//            tt.x_+=d[i][0];tt.y_+=d[i][1];
//            if(st[tt.x_][tt.y_]==0&&Map[tt.x_][tt.y_]=='#')
//            {
//                tt.bits_++;
//                tt.flag_=k;
//                record[tt.x_][tt.y_]=k;
//                q.push(tt);
//            }
//        }
//    }
//}
//int main()
//{
//    int N;
//    cin>>N;
//    int k=1;
//    for(int i=1;i<=N;i++)
//    {
//        for(int j=1;j<=N;j++)scanf("%c",&Map[i][j]);
//    }
//    
//    
//    
//    
//    
//    
//    
//    
//    for(int i=1;i<=N;i++)
//    {
//        for(int j=1;j<=N;j++)
//        {
//            if(st[i][j]==0&&Map[i][j]=='#')
//            {
//                Node t(i,j,0,0);
//                bfs(t,k++);
//            }
//        }
//    }
//
//	set<int> s1;
//    for(int i=1;i<=N;i++)
//    {
//        for(int j=1;j<=N;j++)
//        {
//            if(Map[i][j]!='.'&&Map[i][j]!=0)
//            s1.insert(record[i][j]);
//        }
//    }
////    cout<<endl;
//    
//    
////    
////    cout<<"-----------------------"<<endl;
////     for(int i=1;i<=N;i++)
////    {
////        for(int j=1;j<=N;j++)printf("%c",Map[i][j]);
////        cout<<endl;
////    }
////    cout<<endl;
////    for(int i=1;i<=N;i++)
////    {
////        for(int j=1;j<=N;j++)printf("%d",record[i][j]);
////        cout<<endl;
////    }
////    
////    
////    
////    cout<<endl;
//    
//    for(int i=1;i<=N;i++)
//    {
//        for(int j=1;j<=N;j++)
//        {
//            if(Map[i-1][j]=='.'||Map[i+1][j]=='.'||Map[i][j-1]=='.'||Map[i][j+1]=='.')
//            Map[i][j]='0',record[i][j]=0;
//        }
//    }
////    cout<<"-----------------------"<<endl;
////     for(int i=1;i<=N;i++)
////    {
////        for(int j=1;j<=N;j++)printf("%c",Map[i][j]);
////        cout<<endl;
////    }
////    cout<<endl;
////    for(int i=1;i<=N;i++)
////    {
////        for(int j=1;j<=N;j++)printf("%d",record[i][j]);
////        cout<<endl;
////    }
////    
//    
//  
//    set<int> s2;
//    for(int i=1;i<=N;i++)
//    {
//        for(int j=1;j<=N;j++)
//        {
//            if(Map[i][j]!='.')
//            s2.insert(record[i][j]);
//        }
//    }
//    //set插入O(logN);
//    cout<<s1.size()-s2.size()<<endl;
//    return 0;
//}

//
//#include <bits/stdc++.h>
//using namespace std;
//
//const int N=1e3;
//int a[N][3];
//
//void Print(int n)//打印一个字节
//{
//	int ret[33]={0};
//	int c=32;
//	while(n)
//	{
//		int k=n%2;
//		ret[n--]=k;
//		n/=2;
//	}
//	for(int i=1;i<=32;i++)printf("%d",ret[i]);
//	
//}
//int main()
//{
//	int p[11][33];
//	for(int i=0;i<10;i++)
//	{
//		for(int j=0;j<32;j++)
//		{
//			scanf("%d",&p[i][j]);
//		}
//	}
//	
//	int nx=0,ny=0;
//	for(int i=0;i<10;i++)
//	{
//		for(int j=0;j<32;j++)
//		{
//			if(ny>2)
//			{
//				nx++;
//				ny=0;
//			}
//			a[nx][ny++]=p[i][j];
//		}
//	}
//	
//	
//	for(int i=0;i<160;i++)
//	{
//		for(int j=0;j<2;j++)
//		{
//			Print(a[i][j]);
//		}
//		cout<<endl;
//	}
//	return 0;
//}
//
//



//#include <iostream>
//using namespace std;
//int N = 10;
//int M = 5;
//int main()
//{
//    int a[4][5]={0};
//    int b[5][4]={0};
//    int cnt = 0;
//    for (int i = 0; i < 4; i++)
//    {
//        for (int j = 0; j < 5; j++)
//        {
//            cin >> a[i][j];
//        }
//
//    }
//
//
//    for (int i = 0; i < 4; i++)
//    {
//        for (int j = 0; j < 5; j++)
//        {
//            b[i % 5][j % 4] = a[i][j];
//            cout << b[i % 5][j % 4] << ' ';
//        }
//        cout << endl;
//    }
//    
//    return 0;
//}




//#include <bits/stdc++.h>
//using namespace std;
//int cnt=0;
//void f(int k,int flag)
//{
//	if(k>39)return;
//	if(k==39&&flag%2==0)
//	{
//		cnt++;
//		return;
//	}
//	f(k+1,flag+1);//走两步 ，迈出去再加步 和台阶 
//	f(k+2,flag+1);//走一步 ，迈出去再加步 和台阶 
//}
//
////void f(int k,int flag)
////{
////	if(k<0)return;
////	if(k==0&&flag%2==0)
////	{
////		cnt++;
////		return;
////	}
////	f(k-1,flag+1);
////	f(k-2,flag+1);
////}
//int main()
//{
//	f(0,0);//先左脚 ,一开始没有迈出一步，所以flag为0，迈出去一步flag+1; 
////	f(39,0);
//	cout<<cnt; 
//	return 0;
//}



//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e3;
//double f(double k,int cnt)
//{
//	if(cnt==0)return 1+1/1; 
//	return k+1/f(k,cnt-1);
//}
//int main()
//{
//	double x=f(1,30000);
//	printf("%.100f",1/x);//double精度不够，需要用新的算法来代替 
//	return 0;
//}


//
//#include <bits/stdc++.h>
//using namespace std;
//int main()
//{
//	int a=2;
//	int b=3;
//	int i=0;
//	return 0;
//}


//#include <bits/stdc++.h>
//using namespace std;
//int main()
//{
//	set<char> s;
//	string s1,s2;
//	getline(cin,s1);
//	getline(cin,s2);
//	string ret;
//	for(int i=0;i<s1.size();i++)
//	{
//		
//		if(i<s1.size())
//		{
//				int pos=s2.find(s1[i]);
//			if(pos==string::npos)ret+=s1[i];
//			
//		}
//	}
//	cout<<ret;
//	return 0;
//}


//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e5+10;
//typedef long long ll;
//ll a[N];
//ll s[N];	
//int main()
//{
//	int n;
//	cin>>n;
//	for(int i=1;i<=n;i++)
//	{
//		scanf("%lld",&a[i]);
//		s[i]+=a[i]+s[i-1];
//	}
//	int max=0;
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=i;j<=n;j++)
//		{
//			if(s[j]-s[i]>max)max=s[j]-s[i];
//		}
//	}
//	cout<<max;
//	return 0;
//}

//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e3;
//int a[N];
//int main()
//{
//	int n,target;
//	return 0;
//}




/////////////////////////////////////////////////////////////////////////////////////////////
//2013 蓝桥杯b组 

//1.高斯日记 
//#include <bits/stdc++.h>
//using namespace std;
//const int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
//int main()
//{
//	int year = 1777,month=4,day=30;
//	int k=8112;
//	while(k--)
//	{
//		day++;
//		int val;
//		if(month==2&&((year%4==0&&year%100!=0)||(year%400==0)))
//		val=29;
//		else
//		val=a[month];
//		
//		if(day>val)
//		{
//			day=1;
//			month++;
//			if(month>12)
//			{
//				month=1;
//				year++;
//			}
//		}
//	}
//	cout<<year<<'-'<<month<<'-'<<day<<' ';
//	return 0;
//}

//
////2.马虎的算式
//
//#include <bits/stdc++.h>
//using namespace std;
//int main()
//{
//	int ans=0;
//	for(int a=1;a<=9;a++)
//	{
//		for(int b=1;b<=9;b++)
//		{
//			if(b!=a)
//			{
//				for(int c=1;c<=9;c++)
//				{
//					if(c!=a&&c!=b)
//					{
//						for(int d=1;d<=9;d++)
//						{
//							if(d!=a&&d!=b&&d!=c)
//							{
//								for(int e=1;e<=9;e++)
//								{
//									if(e!=a&&e!=b&&e!=c&&e!=d)
//									{
//										if((a*10+b)*(c*100+d*10+e)==(a*100+d*10+b)*(c*10+e))ans++;
//									}	
//								}	
//							}	
//						}	
//					}	
//				}	
//			} 
//		}
//	}
//	cout<<ans;
//	return 0;
// } 

//3.第39级台阶
//#include <iostream>
//using namespace std;
//int cnt=0;
//void f(int n,int flag)
//{
//  if(n>39)return;
//  if(n==39&&flag%2==0)
//  {
//    cnt++;
//    return;
//  }
//
//  f(n+1,flag+1);
//  f(n+2,flag+1);
//}
//int main()
//{
//  // 请在此输入您的代码
//  f(0,0);
//  cout<<cnt;
//  return 0;
//} 


//4.黄金分割数与fibonacci数列 
//#include <iostream>
//using namespace std;
//int main()
//{
//  // 请在此输入您的代码
//  double a=1.0,b=1.0;//第1 第2
//  int N;
//  cin>>N;
//  N--;
//  if(N>20)N=20;
//  while(N--)
//  {
//    double tmp=b;
//    b=b+a;//第3
//    a=tmp;//第2
//  }
//  double c=a/b;
//  printf("%.8lf",c);
//  return 0;
//}
//





//5.前缀判断
//
//#include <bits/stdc++.h>
//using namespace std;
//
//
//char* start_with(char* haystack_start, char* needle_start)
//{
//    char* haystack = haystack_start;
//    char* needle = needle_start;
//
//    
//    while(*haystack && *needle)//不越界
//    {
//        // if(__________________) return NULL;
//        if(*haystack++!=*needle++)return NULL;
//
//    }
//    
//    if(*needle) return NULL;
//    
//    return haystack_start;
//}
//
//void test(char* a, char* b)
//{
//    char* p = start_with(a,b); 
//    if(p==NULL) 
//        printf("[NO]\n");
//    else 
//        printf("|%s|\n", p);
//}
//
//int main()
//{
//    test("abcd","abc");
//    test("abcd","acb");
//    test("abcd","abcd");
//    test("abcd","");
//    test("","abc");
//    test("","");
//    return 0;
//} 



//6.三部排序-快速排序的三指针法 



//7.票据错误 -sstream的使用


//8.抛硬币 -bfs或找规律

//9.带分数 -全排列next_permutation+切割子串

//10.连号区间 -简单枚举+区间条件判断 









//2014 蓝桥杯B组 

////1.啤酒和饮料
//
//#include <iostream>
//using namespace std;
//int main()
//{
//  // 请在此输入您的代码
//  for(double i=1;i<=100;i++)//饮料
//  {
//    for(double j=1;j<i;j++)//啤酒
//    {
//      if(i*1.9+j*2.3==82.3)
//      {
//        cout<<j<<' ';
//        return 0;
//      }
//    }
//  }
//  return 0;
//}




////2.切面条-- 2*n+1 (n为对折次数) 
//#include <iostream>
//using namespace std;
//int main()
//{
//  // 请在此输入您的代码
//  printf("1025");
//  return 0;
//}


//////3.李白打酒(dfs是记忆化搜索的，递归不是记忆化搜索的。统计次数最好用递归) 
//法1.时间复杂度太大-15的阶乘 
//#include <iostream>
//#include <vector>
////#include <bits/stdc++.h>
//using namespace std;
//const int N = 20;
//char a[N] = { 'D','D','D','D','D','H','H','H','H','H','H','H','H','H','H' };
//vector<char> path;
//int cnt=0;
//bool st[N];
//void dfs(int idex, double sum)
//{
//    if (sum < 0)return;
//    /*cout << "1";*/
//    if (idex > 15)return;
//    if (idex == 15)
//    {
//        cnt++;
//        cout<<cnt<<endl;
//        
//        return;
//    }
//		
//    for (int i = 0; i < 15; i++)
//    {
//        if (!st[i])
//        {
//            st[i] = 1;
//            path.push_back(a[i]);
//            if (a[i] == 'D')
//                dfs(idex + 1, sum * 2);
//            else if (a[i] == 'H')
//                dfs(idex + 1, sum - 1);
//            path.pop_back();
//            st[i] = 0;
//        }
//    }
//}
//
//int main()
//{
//	dfs(0,2);
//	cout<<cnt;
//	return 0;
//}
//法2-递归 
//#include <bits/stdc++.h>
//using namespace std;
//int ans;
//void dfs(int h,int d,double sum)
//{
//	if(d==0&&h==0&&sum==1)ans++;
//	if(h>0)dfs(h-1,d,sum-1);
//	if(d>0)dfs(h,d-1,sum*2);
//}
//int main()
//{
//	dfs(9,5,2);
//	cout<<ans;
//	return 0;
//} 
//法3.next_permutation法 
//#include <bits/stdc++.h>
//using namespace std;
//int ans;
//char arr[15]={'D','D','D','D','D','H','H','H','H','H','H','H','H','H','H'};
//int main()
//{
//
//	do
//	{
//		double sum=2;
//		if(arr[14]=='H')
//		{
//			for(int i=0;i<15;i++)
//			{
//				if(arr[i]=='H')sum-=1;
//				else if(arr[i]=='D')sum*=2;
//			}
//				if(sum==0)ans++;
//		}
//	}
//	while(next_permutation(arr,arr+15));
//	cout<<ans;
//	return 0;
//}



//4.史丰收速算 ***

////5.打印图形 
//
//小明在X星球的城堡中发现了如下图形和文字：
//
//rank=3
//
//   * 
//  * * 
// *   *  
//* * * *
//copy
//rank=5
//
//               *                                                      
//              * *                                                     
//             *   *                                                    
//            * * * *                                                   
//           *       *                                                  
//          * *     * *                                                 
//         *   *   *   *                                                
//        * * * * * * * *                                               
//       *               *                                              
//      * *             * *                                             
//     *   *           *   *                                            
//    * * * *         * * * *                                           
//   *       *       *       *  
//  * *     * *     * *     * *  
// *   *   *   *   *   *   *   * 
//* * * * * * * * * * * * * * * *  
//copy
//rank=6
//
//                               *                                      
//                              * *                                     
//                             *   *                                    
//                            * * * *                                   
//                           *       *                                  
//                          * *     * *                                 
//                         *   *   *   *                                
//                        * * * * * * * *                               
//                       *               *                              
//                      * *             * *                             
//                     *   *           *   *                            
//                    * * * *         * * * *                           
//                   *       *       *       *                          
//                  * *     * *     * *     * *                         
//                 *   *   *   *   *   *   *   *                        
//                * * * * * * * * * * * * * * * *                       
//               *                               *                      
//              * *                             * *                     
//             *   *                           *   *                    
//            * * * *                         * * * *                   
//           *       *                       *       *                  
//          * *     * *                     * *     * *                 
//         *   *   *   *                   *   *   *   *                
//        * * * * * * * *                 * * * * * * * *               
//       *               *               *               *              
//      * *             * *             * *             * *             
//     *   *           *   *           *   *           *   *            
//    * * * *         * * * *         * * * *         * * * *           
//   *       *       *       *       *       *       *       *          
//  * *     * *     * *     * *     * *     * *     * *     * *         
// *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *        
//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *       
//copy
//小明开动脑筋，编写了如下的程序，实现该图形的打印。
//
//请分析程序流程，填写划线部分缺少的代码。
//
//源代码
//C
//
//#include <stdio.h>
//#define N 70
//#define M 35
//
//void f(char a[][N], int rank, int row, int col)
//{
//    if(rank==1){
//        a[row][col] = '*';
//        return;
//    }
//    
//    int w = 1;
//    int i;
//    for(i=0; i<rank-1; i++) w *= 2;
//    
//    __________________;
//    f(a, rank-1, row+w/2, col);
//    f(a, rank-1, row+w/2, col+w);
//}
//
//int main()
//{
//    char a[M][N];
//    int i,j;
//    for(i=0;i<M;i++)
//    for(j=0;j<N;j++) a[i][j] = '.';
//    
//    f(a,6,0,0);
//    
//    for(i=0; i<M; i++){
//        for(j=0; j<N; j++) printf("%c",a[i][j]);
//        printf("\n");
//    }
//    
//    return 0;
//}
//
//copy
//运行限制
//最大运行时间：1s
//最大运行内存: 128M

//#include <stdio.h>
//#define N 70
//#define M 35
//
//void f(char a[][N], int rank, int row, int col)
//{
//	if(rank==1){
//		a[row][col] = '*';
//		return;
//	}
//	
//	int w = 1;
//	int i;
//	for(i=0; i<rank-1; i++) w *= 2;//2^5=32;  2^4=16;  2^3=8; 2^2=4; 2^1=2;
//	
////	
//	f(a, rank-1, row, col+w/2);
//	f(a, rank-1, row+w/2, col);//a,5,16,0;a,4,24,0;  a,3,28,0;  a,2,30,0; a,1,31,0;
//	f(a, rank-1, row+w/2, col+w);//a,5,16,32;a,4,24,48; a,3,28,56; a,2,30,60; a,1,31,62;
//
//  //三个顶点
//}
//
//int main()
//{
//	char a[M][N];
//	int i,j;
//	for(i=0;i<M;i++)
//	for(j=0;j<N;j++) a[i][j] = '.';
//	
//	f(a,6,0,0);
//	
//	for(i=0; i<M; i++){
//		for(j=0; j<N; j++) printf("%c",a[i][j]);
//
//		printf("\n");
//	}
//	
//	return 0;
//}







//////6.奇怪的分式-浮点数比较需要用到fbs(a,b)<1e-5;此时浮点数a才等于浮点数b 
//#include <bits/stdc++.h>
//using namespace std;
//
//int ans=0;
//
//int main() 
//{
//	for(double x1=1;x1<=9;x1++)
//	{
//		for(double y1=1;y1<=9;y1++)
//		{
//				for(double x2=1;x2<=9;x2++)
//				{
//					for(double y2=1;y2<=9;y2++)
//					{
//						if(y2!=x2||y1!=x1)
//						{
//							 if(fabs((x1/y1)*(x2/y2)-(x1*10+x2)/(y1*10+y2))<1e-5)
//           						 ans++;  
//						}
//						
//					}
//				}
//			
//		}
//	}
//	cout<<ans;
////	cout<<gcd(15,30);
//	return 0; 
//}





//////7.六角填数 -next_permutation全排列 + 逻辑化图像
// 
//法1.手写12重循环-不推荐，难调试 
//#include <bits/stdc++.h>
//using namespace std;
//int a[13];
//int main()
//{
//	a[1]=1;
//	a[2]=8;
//	a[12]=3;
//	map<int,int> mp;
//	mp[a[1]]++;
//	mp[a[2]]++;
//	mp[a[12]]++;
//	
//	for(int a3=2;a3<=12;a3++)
//	{
//		
//		if(!mp.count(a3))
//		{
//			mp[a3]++;
//			for(int a4=2;a4<=12;a4++)
//			{
//			
//				if(!mp.count(a4))
//				{
//				mp[a4]++;
//					for(int a5=2;a5<=12;a5++)
//					{	
//					
//						if(!mp.count(a5))
//						{	
//						mp[a5]++;
//							for(int a6=2;a6<=12;a6++)
//							{
//								
//								if(!mp.count(a6))
//								{	{mp[a6]++;
//									for(int a7=2;a7<=12;a7++)
//								
//									
//										if(!mp.count(a7))
//										{mp[a7]++; 
//											for(int a8=2;a8<=12;a8++)
//											{	
//											
//												if(!mp.count(a8))
//												{	mp[a8]++;
//														
//													for(int a9=2;a9<=12;a9++)
//													{
//														if(!mp.count(a9))
//														{	mp[a9]++;
//															for(int a10=2;a10<=12;a10++)
//															{
//														 
//																if(!mp.count(a10))
//																{	mp[a10]++;
//																	for(int a11=2;a11<=12;a11++)
//																	{
//																		
//																		if(!mp.count(a11))
//																		{
//																			mp[a11]++;
//																			for(int a12=2;a12<=12;a12++)
//																			{
//																				
//																				cout<<a6<<' ';
//																				
//																			}
//																			mp[a11]--;
//																		}
//																		
//																	}
//																	mp[a10]--;
//																}
//															
//															}
//																mp[a9]--;
//														}
//												
//													}
//														mp[a8]--;
//												}
//										
//											}
//												mp[a7]--;
//										}
//								
//									}
//									mp[a6]--;
//								}
//							
//							}
//						mp[a5]--;
//						}
//					
//					}
//					mp[a4]--;
//				}
//			
//			}
//			mp[a3]--;
//		}
//		
//	}
//	return 0;
//}
//法2.用库函数 next_permutation()列出全排列 
//#include <bits/stdc++.h>
//using namespace std;
//int a[13]={0,1,2,3,4,5,6,7,8,9,10,11,12};
//int main()
//{
//	do
//	{
//		if(a[1]==1&&a[2]==8&&a[12]==3)
//		{
//			int line1=a[1]+a[3]+a[6]+a[8];
//			int line2=a[1]+a[4]+a[7]+a[11];
//			int line3=a[8]+a[9]+a[10]+a[11];
//			int line4=a[12]+a[9]+a[6]+a[2];
//			int line5=a[12]+a[10]+a[7]+a[5];
//			int line6=a[2]+a[3]+a[4]+a[5];
//			if(line1==line2&&line2==line3&&line3==line4&&line4==line5&&line5==line6)
//			{
//				cout<<a[6];
//				return 0;
//			}
//		}
//	}
//	while(next_permutation(a+1,a+13));//左闭右开 
//	return 0;
//}

//8.蚂蚁感冒 

//9.地宫取宝
//题目描述
//X 国王有一个地宫宝库。是 n \times mn×m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
//
//地宫的入口在左上角，出口在右下角。
//
//小明被带到地宫的入口，国王要求他只能向右或向下行走。
//
//走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
//
//当小明走到出口时，如果他手中的宝贝恰好是 kk 件，则这些宝贝就可以送给小明。
//
//请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 kk 件宝贝。
//
//输入描述
//输入一行 3 个整数，用空格分开：n, m, k\ (1 \leq n,m \leq 50, 1 \leq k \leq 12)n,m,k (1≤n,m≤50,1≤k≤12)。
//
//接下来有 nn 行数据，每行有 mm 个整数 C_i\ (0 \leq C_i \leq 12)C 
//i
//?
//  (0≤C 
//i
//?
// ≤12) 代表这个格子上的宝物的价值。
//
//输出描述
//要求输出一个整数，表示正好取 kk 个宝贝的行动方案数。该数字可能很大，输出它对 10^9+710 
//9
// +7 取模的结果。
//
//输入输出样例
//示例
//输入
//
//2 2 2
//1 2
//2 1
//copy
//输出
//
//2
//#include <bits/stdc++.h>
//using namespace std;
//const int N=50;
//long long ans;
//long long val[N][N];
//int n,m,k;
////由于dfs的时间复杂度过高，我们可以进行剪枝
//
//
//void dfs(int x,int y,int k,long long max)
//{
//	if(x>=n||y>=m||k<0)return;
//	if(x==n-1&&y==m-1)
//	{
//    if(k==0||(k==1&&val[x][y]>max))
//		ans=(ans+1)%1000000007; 
//		return;
//	}
//   if(n-1-x+1+m-1-y+1<k)//剪枝
//   return;
//	
//	if(val[x][y]>max)//大于任意的，可以拿可以不拿 
//	{
//		////拿 
//		//往下 
//    if(x+1<n)
//		dfs(x+1,y,k-1,val[x][y]);
//		//往右
//    if(y+1<m)
//		dfs(x,y+1,k-1,val[x][y]);
//		
//    //只有后面的次数足够的时候才可以不拿，如果后面次数不够，满足条件的话我们就必须得拿
//		////不拿
//		//往下
//     if(n-1-x+1+m-1-y+1>=k)//剪枝
//    {
//		if(x+1<n)
//		dfs(x+1,y,k,max);
//		//往右
//		if(y+1<m)
//		dfs(x,y+1,k,max); 
//    }
//	}
//	else//不大于任意的，则不可以拿-注意不要漏掉了val[x][y]>max的dfs，他和val[x][y]<max不是同一次dfs的，不要合并了。
//	{
//    //只有后面的次数足够的时候才可以不拿，如果后面次数不够，满足条件(val[x][y]>max)的话我们就必须得拿
//    //只有后面的次数足够的时候才可以不拿
//		////不拿
//   
//    //往下
//    if(x+1<n)
//		dfs(x+1,y,k,max);
//		//往右
//    if(y+1<m)
//		dfs(x,y+1,k,max); 
//	} 
//}
//int main()
//{
//
//	cin>>n>>m>>k;
//	for(int i=0;i<n;i++)
//	{
//		for(int j=0;j<m;j++)
//		cin>>val[i][j];
//	}
//	dfs(0,0,k,-1);
//	cout<<ans%1000000007;
//	return 0;
//} 
//	
	
	
//10.小朋友排队 
	

/////////////////////////////////////////////////////////////////////////////////////////////

//2015 蓝桥杯B组 
////1.奖券数目
//#include <bits/stdc++.h>
//using namespace std;
//int main()
//{
//	int cnt=0;
//	for(int i=10000;i<=99999;i++)
//	{
//		int tmp=i;
//		bool flag=true;
//		while(tmp)
//		{
//			int k=tmp%10;
//			tmp/=10;
//			if(k==4)
//			{
//				flag=false;
//				break;
//			}
//		}
//		if(flag)cnt++;
//	}
//	cout<<cnt;
//	return 0;
//}

////2.星系炸弹 
//#include <bits/stdc++.h>
//using namespace std;
//static int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
//
//int main()
//{
//	int year=2014,month=11,day=9;
//	int k=1000;
//	while(k--)
//	{
//		day++;
//		int val;
//		if(month==2&&((year%4==0&&year%100!=0)||year%400==0))val=29;
//		else val=a[month];
//		if(day>val)
//		{
//			day=1;
//			month++;
//			if(month>12)
//			{
//				year++;
//				month=1;
//			}
//		}
//	}
//	cout<<year<<' '<<month<<' '<<day;
//	return 0;
//}


//3.三羊献瑞
//      祥 瑞 生 辉
//  +   三 羊 献 瑞
//-------------------
//   三 羊 生 瑞 气
//#include <bits/stdc++.h>
//using namespace std;
//int a,b,c,d,e,f,g,h,i; 
////三、羊 
//int main()
//{
//	
//	return 0;
//}

////4.格子中输出
//#include <stdio.h>
//#include <string.h>
//
//void StringInGrid(int width, int height, const char* s)
//{
//    int i,k;
//    char buf[1000];
//    strcpy(buf, s);
//    if(strlen(s)>width-2) buf[width-2]=0;
//    
//    printf("+");
//    for(i=0;i<width-2;i++) printf("-");
//    printf("+\n");
//    
//    for(k=1; k<(height-1)/2;k++){
//        printf("|");
//        for(i=0;i<width-2;i++) printf(".");
//        printf("|\n");
//    }
//    
//    printf("|");
//    
////    printf("%*s%s%*s",__________________);
//              
//    printf("|\n");
//    
//    for(k=(height-1)/2+1; k<height-1; k++){
//        printf("|");
//        for(i=0;i<width-2;i++) printf(".");
//        printf("|\n");
//    }    
//    
//    printf("+");
//    for(i=0;i<width-2;i++) printf("-");
//    printf("+\n");    
//}
//
//int main()
//{
//    StringInGrid(10,4,"abcd123");
//    return 0;
//} 


////5.九数组分数 
//#include <stdio.h>
//void test(int x[])
//{
//    int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
//    int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];
//    
//    if(a*3==b) printf("%d/%d\n", a, b);
//}
//void f(int x[], int k)
//{
//    int i,t;
//    if(k>=9)
//	{
//        test(x);
//        return;
//    }
//    
//    for(i=k; i<9; i++)
//	{
//        {//swap x[k]和x[i] 
//			 t=x[k]; 
//			 x[k]=x[i];
//			 x[i]=t;
//		}
//        f(x,k+1);
//		{//swap x[k]和x[i] 
//			 t=x[i]; 
//			 x[i]=x[k];
//			 x[k]=t;
//		}	
//    }
//}
//int main()
//{
//    int x[] = {1,2,3,4,5,6,7,8,9};
//    f(x,0);    
//    return 0;
//}
//

////6.加法变乘法
//#include <bits/stdc++.h>
//using namespace std;
//const int N=55;
//char a[N];
//
//int main()
//{
//	a[1]='*';
//	a[2]='*';
//	for(int i=3;i<=48;i++)
//	{
//		a[i]='+';
//	}
//	
//	do
//	{
//		int ret[N]={0};
//		for(int i=1;i<=49;i++)ret[i]=i;
//		
//		int sum=0;
//		int pos[2]={0};
//		int ans[2]={0};
//		int j=0;
//		for(int i=1;i<=48;i++)
//		{
//			if(a[i]=='*')pos[j++]=i;
//			if(j==2)break;
//		}
//		for(int j=0;j<2;j++)
//		{
//			ret[pos[j]+1]*=ret[pos[j]];
//			ans[j]=ret[pos[j]];
//			ret[pos[j]]=0;
//		}
//		for(int i=1;i<=49;i++)sum+=ret[i]; 
//		if(sum==2015)
//		{
//			if(ans[0]!=10)
//			{
//				cout<<ans[0];
//				return 0;
//			}
//			
//		}
////		for(int i=1;i<=48;i++)cout<<a[i]<<' ';
////		cout<<endl;
//	}
//	while(next_permutation(a+1,a+49)); 
//	return 0;
//} 




//7.牌型种类 
//#include <bits/stdc++.h>
//using namespace std;
//int main()
//{
//	return 0;
//}
//














/////////////////////////////////////////////////////////////////////////////////////////////
//2022 蓝桥杯B组 
//1.九进制转十进制 100%
//#include <iostream>
//using namespace std;
//int main()
//{
//  // 请在此输入您的代码
//  int sum=2*1 +2*9+ 0*9*9+ 2*9*9*9;
//  printf("%d",sum);
//  return 0;
//} 



//2.顺子日期 100%
//#include <bits/stdc++.h>
//#include <iostream>
//#include <string>
//using namespace std;
//int a[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//int main()
//{
//    int cnt = 0;
//    int year = 2022, month = 1, day = 1;
//    while (true)
//    {
//        if (year == 2023 && month == 1 && day == 1)break;
//
//        day++;
//        int val;
//        if (month == 2 && ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)))val = 29;
//        else val = a[month];
//
//        if (day > val)
//        {
//            month++;
//            day = 1;
//            if (month > 12)
//            {
//                year++;
//                month = 1;
//            }
//        }
//
//        string cur= to_string(year);
//
//        if (month < 10)cur +='0';
//        cur += to_string(month);
//
//        if (day < 10)cur += '0';
//        cur += to_string(day);
//
//        string sub = cur.substr(4);
//        //cout << sub<<endl;
//        if ((sub[0] == sub[1] - 1 && sub[1] == sub[2] - 1) || (sub[1] == sub[2] - 1 && sub[2] == sub[3] - 1))cnt++;
//    
//    }
//    cout << cnt;
//    return 0;
//}


//3.刷题统计 100%
//输出格式
//输出一个整数代表天数。
//
//样例输入
//10 20 99
//copy
//样例输出
//8
//copy
//评测用例规模与约定
//对于 50 \%50% 的评测用例, 1 \leq a, b, n \leq 10^{6}1≤a,b,n≤10 
//6
// .
//
//对于 100 \%100% 的评测用例, 1 \leq a, b, n \leq 10^{18}1≤a,b,n≤10 
//18
// .
//
//运行限制
//最大运行时间：1s
//最大运行内存: 256M 
//#include <bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//int main()
//{
//	ll a,b,n;
//	cin>>a>>b>>n;
//  if(n<0)
//  {
//    cout<<0;
//    return 0;
//  }
//	ll cnt=0;
//	ll weekwork=5*a+2*b;
//	ll weekcnt=n/weekwork;
//	cnt+=7*weekcnt;
//	n-=weekcnt*weekwork;
//	for(int i=1;i<=7;i++)
//	{
//		if(n<=0)break;
//		if(i>=1&&i<=5)
//		{
//			n-=a;
//			cnt++;
//		}
//		else if(i>=6&&i<=7)
//		{
//			n-=b;
//			cnt++;
//		}
//	}
//	cout<<cnt;
//	return 0;
//}



////4.修建灌木 100%
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e5+10;
//int a[N],b[N];
//int amax[N];//存最大的 
//
//int main()
//{	
//	int n;
//	cin>>n;
//	int cnt=0;
//	for(int j=1;j<=n;j++)
//	{
//		for(int i=1;i<=n;i++)
//		{
//			a[i]++;
//			amax[i]=max(amax[i],a[i]);
//		}
//		a[j]=0;
//		if(j==n)
//		{
//			if(cnt==3)break;
//			cnt++;
//			for(int x=n-1;x>=1;x--)
//			{
//				for(int y=1;y<=n;y++)
//				{
//					a[y]++;
//					amax[y]=max(amax[y],a[y]);
//				}
//				a[x]=0;
//				if(x==1)
//				{
//					j=1;
//					break;
//				}
//			}
//		}
//	}
//	for(int i=1;i<=n;i++)cout<<amax[i]<<endl;
//	return 0;
//} 

//5.X进制减法   最好将数位都逆序过来，或一开始就逆序输入，才能对齐 

//问题描述
//
//进制规定了数字在数位上逢几进一。
//
//X 进制是一种很神奇的进制，因为其每一数位的进制并不固定!例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则X进制数 321 转换为十进制数为 65。
//
//现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。请你算出 A-B 的结果最小可能是多少。
//
//输入格式??
//
//第一行一个正整数 N，含义如题面所述。
//第二行一个正整数 Ma，表示 X 进制数 A 的位数。
//第三行 Ma 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。
//第四行一个正整数 M, 表示X进制数 B 的位数。
//第五行 Mb 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各个数位上的数字在十进制下的表示。
//请注意，输入中的所有数字都是十进制的。
//
//输出格式
//
//输出一行一个整数，表示X进制数 A - B 的结果的最小可能值转换为十进制后再模1000000007的结果。
//
//样例输入
//
//11
//
//3
//
//10 4 0
//
//3
//
//1 2 0
//
//样例输出
//
//94
//
//样例说明 
//
//当进制为:最低位2进制，第二数位5进制，第三数位11进制时,减法得到的差最小。此时A在十进制下是108，B在十进制下是 14，差值是94.
//
//评测用例规模与约定
//
//对于30%的数据，N≤ 10; Ma, Mb ≤ 8.
//对于100%的数据，2 < N ≤ 1000; 1 ≤ Ma, Mb, ≤ 100000; A ≥ B.

//#include <bits/stdc++.h>
//using namespace std;
//const int u=1e5+10;
//typedef long long ll;
//int N;
//ll Ma;
//ll A[u];
//ll Mb;
//ll B[u];
//ll jinzhi[u];
//
//int main()
//{
//	cin>>N;
//	cin>>Ma;
//	for(int i=1;i<=Ma;i++)
//	{
//		scanf("%lld",&A[i]);
//	}
//	cin>>Mb;
//	for(int i=1;i<=Mb;i++)
//	{
//		scanf("%lld",&B[i]);
//	}
//	reverse(A+1,A+Ma+1);
//	reverse(B+1,B+Mb+1);
//	int n=Ma,m=Mb;
//	jinzhi[0]=1;
//
//
//	for(int i=1;i<=Ma;i++)
//	{
//		jinzhi[i]=(max( max(A[i] ,B[i])+1   ,  (long long)2  )   *jinzhi[i-1])%   1000000007;
//	}
//
//
//
//	ll sum=0;
//	for(int i=1;i<=Ma;i++)
//	{
//		sum=(sum+(A[i]-B[i])*jinzhi[i-1])%1000000007;
//	}
//
//	cout<<sum%1000000007;
//	return 0;
//}
//
//






//6.统计子矩阵 70%
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e3;
//typedef long long ll;
//ll a[N][N],s[N][N];
//int main()
//{
//	int n,m;
//	cin>>n>>m;
//	ll k;
//	cin>>k;
//	ll cnt=0; 
//	for(int i=1;i<=n;i++)
//	{
//		
//		for(int j=1;j<=m;j++)
//		{
//			scanf("%lld",&a[i][j]);
//		}
//		
//	}
//	
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++)s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
//	}
//	
//	for(int x1=1;x1<=n;x1++)
//	{
//		for(int y1=1;y1<=m;y1++)
//		{
//			for(int x2=x1;x2<=n;x2++)
//			{
//				for(int y2=y1;y2<=m;y2++)
//				{
//					ll ret=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
//					if(ret<=k)cnt++;
//				}
//			}
//		}
//	}
//	cout<<cnt;
//	return 0;
//} 



//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e3;
//int a[N][N];
//typedef long long ll;
//int main()
//{
//	int n,m;
//	ll k;
//	cin>>n>>m>>k;
//	int cnt=0;
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++)
//		{
//			scanf("%d",&a[i][j]);
//			a[i][j]+=a[i-1][j];
//		}
//	}
//	for(int u=1;u<=n;u++)//上闭下闭 
//	{
//		for(int d=1;d<=n;d++)
//		{
//			
//			int l=1,r=1;
//			for(r=1;r<=m;r++)
//			{
//				ll sum=0;
//				for(int i=l;i<=r;i++)	
//				{
//					sum+=(a[d][i]-a[u-1][i]);
//				}
//				while(sum>k)
//				{
//					sum-=(a[d][l]-a[u-1][l]);
//					l++;
//				}
//				cnt+=r-l+1;
//			}
//		}	
//	} 
//	cout<<cnt;
//	return 0;
//}

////7.扫雷 100%
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e2+20;
//int a[N][N];//有无地雷 
//int st[N][N];//记录周围有多少地雷 
//int d[9][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
//int main()
//{
//	int n,m;
//	cin>>n>>m;
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++)
//		{
//			scanf("%d",&a[i][j]);
//		
//		}
//	}
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++)
//		{
//			if(a[i][j]==0)
//			{
//				int cnt=0;
//				for(int k=0;k<9;k++)
//				{
//				cnt+=(a[i+d[k][0]][j+d[k][1]]==1);
//				}
//				st[i][j]=cnt;
//			}
//			else if(a[i][j]==1)st[i][j]=9;
//		}
//	}
//	cout<<endl;
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++)
//		{
//			cout<<st[i][j]<<' ';
//		}
//		cout<<endl;
//	}
//	return 0;
//} 


//8.李白打酒加强版 40%
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e2+10;
//typedef long long ll;
//int a[N];
//int cnt=0;
//int main()
//{
//	int n,m;
//	cin>>n>>m;
//	int idex=1;
//	int x=n,y=m;
//	while(x--)
//	{
//		a[idex++]=1;//店 
//	}
//	while(y--)
//	{
//		a[idex++]=2;//花 
//	}
//	int k=n+m;
//	
//	
//	do
//	{
//		bool flag=true;
//		double sum=2.0;
//		int i=1;
//		for( i=1;i<=k;i++)
//		{
//			if(sum<0)
//			{
//				flag=false;
//				break;
//			}
//			if(a[i]==2)sum-=1;
//			else if(a[i]==1)sum*=2;
//		}
//		if(sum==0&&flag&&i==k+1&&a[k]==2)cnt++;
//	}
//	while(next_permutation(a+1,a+k+1));
//
//
//
//	cout<<cnt%(1000000007);
//	return 0;
//	
//} 




/////////////////////////////////////////////////////////////////////////////////////////////




//2022 蓝桥杯 A组

////1.裁纸刀 -找规律(递推找规律或直接看出公式)本题是直接看出公式  100%
// #include <bits/stdc++.h>
//using namespace std;
//int main()
//{
//
//  int n=20,m=22;
//
//  printf("%d",4+(n-1)+(m-1)*n);
//  return 0;
//}
 
//2.灭鼠先锋 贪心? 

////3.求和 60%
//#include <bits/stdc++.h>
//using namespace std;
//const int N=2*1e5+10;
//int a[N];
//typedef long long ll;
//int main()
//{
//	int n;
//	cin>>n;
//	ll sum=0;
//	for(int i=1;i<=n;i++)
//	{
//		scanf("%lld",&a[i]);
//	}
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=i+1;j<=n;j++)
//		{
//			sum+=a[i]*a[j];
//		}
//	}
//	cout<<sum;
//	return 0;
//}

////4.选数异或 40%
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e5+10;
//typedef long long ll;
//ll a[N];
//int main()
//{
//	int n,m,k;
//	cin>>n>>m>>k;
//	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
//	while(m--)
//	{
//		int l,r;
//		scanf("%d %d",&l,&r);
//		int flag=false;
//		for(int i=l;i<=r;i++)
//		{
//			for(int j=i+1;j<=r;j++)
//			{
//				if((a[i]^a[j])==k)
//				{
//					flag=true;
//					break;
//				}
//			}
//			if(flag)break;
//		}
//		
//		if(flag)cout<<"yes";
//		else cout<<"no";
//		
//		cout<<endl;
//	
//	}
//	return 0;
//} 

////5.爬树的甲壳虫
//
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e5+10;
//double a[N];//递达i层的概率 
//double P=0;//期望 
//int main()
//{
//	int n;
//	cin>>n;
//	a[0]=1;
//	for(int i=1;i<=n;i++)
//	{
//		int x,y;
//		scanf("%d %d",&x,&y);
//		a[i]=a[i-1]*(1.0-x/y);
//	}
//	for(int i=1;i<=n;i++)
//	{
//		P+=(a[i])*
//	}
//	return 0;
//} 




//2021


//#include <bits/stdc++.h>
//using namespace std;
//int a[10];
//bool f(int n)
//{
//	while(n)
//	{
//		int val=n%10;
//		
//	
//		
//		if(a[val]!=0)
//		a[val]--;
//		
//		else
//		return false;
//		
//		n/=10;
//	}
//	return true;
//}
//int main()
//{
//	for(int i=0;i<=9;i++)a[i]=2021;
//
//	for(int i=0;i<=20210;i++)
//	{
//		bool flag=f(i);
//		if(!flag)
//		{
//			cout<<i<<endl;
//			break;
//		}
//	}
//	return 0;
//}

////2.货物摆放
//#include <bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//ll n;
//int cnt;
//
//
//void dfs(int idex,ll sum,int d)//回溯
//{
//	if(sum>n)return;
//	if(idex==3)
//	{
//		if(sum==n)
//		{
//			cnt++;
////			cout<<cnt;
//		}
//		return ;
//	}
//
//	for(int i=d;i<sqrt(n);i++)
//	{
//		dfs(idex+1,sum*i,i);
////		cout<<cnt<<endl;
//	}
//}
//int main()
//{
//	cin>>n;
//	dfs(0,1,1);
//	cout<<cnt;
//	return 0;
//}



////3.路径
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e4;
//typedef long long ll;
//
//#define INT 0x3f3f3f3f
//ll edge[2022][2022];//表示两点之间边最短的长度
//int gcd(int a,int b)
//{
//	if(b==0)return a;
//	return gcd(b,a%b);
//}
//int lcm(int a,int b)
//{
//	int ret=a*b;
//	return ret/gcd(a,b);
//}
//int main()
//{
//	memset(edge,INT,sizeof(edge));
//	for(int i=1;i<=2021;i++)
//	{
//		for(int j=1;j<=2021;j++)
//		{
//			if(i==j)edge[i][j]=0;
//			else if(abs(i-j)<=21)
//			{
//				edge[i][j]=lcm(i,j);//存在一条最小公倍数的边
//			}
//		}
//	}
//
//	for(int k=1;k<=2021;k++)
//	{
//		for(int j=1;j<=2021;j++)
//		{
//			for(int i=1;i<=2021;i++)//中间的一个节点
//			{
//				edge[j][i]=min(edge[j][i],edge[j][k]+edge[k][i]);
//			}
//		}
//	}
//	cout<<edge[1][2021];
//	return 0;
//}

//七段码
//#include <bits/stdc++.h>
//using namespace std;
//const int N = 1e2;
//int e[8][8];
//int used[8];
//int p[N];
//
//void init()
//{
//	for (int i = 1; i <= 7; i++)
//	{
//		p[i] = i;
//	}
//}
//int find(int x)
//{
//	if (p[x] != x)p[x] = find(x);
//	return p[x];
//}
//
//int res = 0;
//void dfs(int idex)
//{
//	if (idex > 7)
//	{
//		init();
//		cout<<2;
//		for (int i = 1; i <= 7; i++)
//		{
//			for (int j = 1; j <= 7; j++)
//			{
//				cout<<3;
//				if (used[i] == 1 && used[j] == 1 && e[i][j] == 1)
//				{
//					int fa = find(i),fb=find(j);
//					if (fa != fb)p[fa] = fb;
//				}
//			}
//			int cnt = 0;
//			for (int i = 1; i <= 7; i++)
//			{
//				if (used[i]==1&&i == find(i))cnt++;//连通分支数
//			}
//			if (cnt == 1)res++;
//		}
//
//		return;
//	}
// cout << 1;
//	used[idex] = 1;
//	dfs(idex + 1);
//	used[idex] = 0;
//	dfs(idex + 1);
//}
//int main()
//{
//	//a1,b2,c3,d4,e5,f6,g7
//
//	e[1][6] = e[1][2] = 1;
//	e[2][1] = e[2][3] = e[2][7] = 1;
//	e[3][2] = e[3][7] = e[3][4] = 1;
//	e[4][3] = e[4][5] = 1;
//	e[5][4] = e[5][7] = e[5][6] = 1;
//	e[6][7] = e[6][1] = e[6][5] = 1;
//	e[7][2] = e[7][3] = e[7][5] = e[7][6] = 1;
//	dfs(1);
//	cout << res << endl;
//	return 0;
//}


#include <bits/stdc++.h>
using namespace std;
unsigned long long res;
const int N = 1e5 + 10;
vector<int> a(N, 0);

void merge_sort(vector<int>& q, int l, int r)//归并排序求逆序对
{

	if (l >= r)return;
	int mid = l + r >> 1;
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);
	int k = 0, i = l, j = mid + 1;
	int tmp[r - l + 1];
	while (i <= mid && j <= r)
	{
		if (q[i] <= q[j])tmp[k++] = q[i++];
		else
		{
			tmp[k++] = q[j++];
			res += (mid - i + 1);
		}
	}
	while (i <= mid)
	{
		tmp[k++] = q[i++];
	}
	while (j <= r)
	{
		tmp[k++] = q[j++];
	}
	for (int i = l, j = 0; i <= r; i++, j++)q[i] = tmp[j];
}
void shift_plus(vector<int>& q, int l, int r, int k)//右移k位
{
	int tmp[N / 100];
	for (int i = l; i <= r; i++)
	{
		int idex = i + k;
		while (idex > r)idex -= (r - l + 1);
		tmp[idex] = q[i];
	}
	for (int i = l; i <= r; i++)q[i] = tmp[i];
}
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)a[i] = i;
	res = 0;

	while (m--)
	{
		int l, r, k;
		cin >> l >> r >> k;
		shift_plus(a, l, r, k);

		merge_sort(a, 1, n);
		if (res % 2 == 1)cout << "huai" << endl;
		else cout << "hao" << endl;
	}
	return 0;
}
